package algotithm.weekendrace.leetcode244.test3;

/**
 * @author 25068
 * @Date 2021/6/6 12:13
 * @Title 5778. 使二进制字符串字符交替的最少反转次数
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "111000";
        int res = solution.minFlips(s);
        System.out.println(res);
    }

    public int minFlips(String s) {
        int n = s.length();
        char[] c = s.toCharArray();
        int [][] l = new int[2][n];
        int [][] r = new int[2][n];
        if(c[0] == '0') {
            l[1][0]++;
        } else {
            l[0][0]++;
        }
        if(c[n - 1] == '0') {
            r[1][0]++;
        } else {
            r[0][0]++;
        }
        for(int i = 1; i < n; i++) {
            l[0][i] = l[1][i - 1] + (c[i] != '0' ? 1 : 0);
            l[1][i] = l[0][i - 1] + (c[i] != '1' ? 1 : 0);
            r[0][i] = r[1][i - 1] + (c[n - i - 1] != '0' ? 1 : 0);
            r[1][i] = r[0][i - 1] + (c[n - i - 1] != '1' ? 1 : 0);
        }
        /*
        System.out.println(Arrays.toString(l[0]));
        System.out.println(Arrays.toString(l[1]));
        System.out.println(Arrays.toString(r[0]));
        System.out.println(Arrays.toString(r[1]));
        System.out.println();*/
        if(n % 2 == 0) {
            return Math.min(l[0][n - 1], l[1][n - 1]);
        }
        int res = Math.min(l[0][n - 1], l[1][n - 1]);
        for(int i = 1; i < n - 1; i++) {
            res = Math.min(res, Math.min(l[0][i], l[1][i]) + Math.min(r[0][n - i - 2], r[1][n - i - 2]));
        }
        return res;
    }
}
